from cPickle import load
from McTree import *
import os
from time import clock

fibostr = ()
fibono = 1
def restartFibStr():
	global fibono, fibostr
	fibostr = ('b','a')
	fibono = 1
restartFibStr() 
def getNextFibStr():
	'''
	Increases the Fibonacci string to the next counter
	and returns it.
	''' 
	global fibostr, fibono
	newstr = fibostr[0]+fibostr[1]
	fibostr = (fibostr[1], newstr)
	fibono += 1
	return newstr
def getFibStr(no):
	global fibostr, fibono
	if fibono == no:
		return fibostr[1]
	if fibono == no-1:
		return fibostr[0]
	if fibono > no:
		restartFibStr()
		return getFibStr(no)
	while fibono < no:
		res = getNextFibStr()
	return res	



#make tree over fibostring.
def makeTree(no):
	picklefile = 'trees/Fibonacci-tree-%02d.pickle' %no
	#if os.path.exists(picklefile):
	try:
		return load(open(picklefile, 'rb'))
	except:
		string = getFibStr(no)
		return McTree(string)

def countInternalNodes(node):
	res = len(node)
	for n in node.edges.itervalues():
		if isinstance(n, InnerNode):
			res += countInternalNodes(n)
	return res


for i in xrange(9, 28):
	start = clock()
	tree = makeTree(i)
	builded = clock()
	number = countInternalNodes(tree.root)
	stop = clock()
	print "Fib. no. %i has %i internal nodes (Builded in %d ms, counted in %d ms)." %(i, number, (builded-start)*1000, (stop-builded)*1000)
	
# Output
#Fib. no. 9 has 88 internal nodes (Builded in 9 ms, counted in 0 ms).
#Fib. no. 10 has 143 internal nodes (Builded in 0 ms, counted in 0 ms).
#Fib. no. 11 has 232 internal nodes (Builded in 0 ms, counted in 0 ms).
#Fib. no. 12 has 376 internal nodes (Builded in 10 ms, counted in 0 ms).
#Fib. no. 13 has 609 internal nodes (Builded in 10 ms, counted in 0 ms).
#Fib. no. 14 has 986 internal nodes (Builded in 20 ms, counted in 0 ms).
#Fib. no. 15 has 1596 internal nodes (Builded in 79 ms, counted in 0 ms).
#Fib. no. 16 has 986 internal nodes (Builded in 40 ms, counted in 0 ms).
#Fib. no. 17 has 4180 internal nodes (Builded in 200 ms, counted in 10 ms).
#Fib. no. 18 has 2583 internal nodes (Builded in 120 ms, counted in 10 ms).
#Fib. no. 19 has 10945 internal nodes (Builded in 500 ms, counted in 20 ms).
#Fib. no. 20 has 6764 internal nodes (Builded in 310 ms, counted in 10 ms).
#Fib. no. 21 has 28656 internal nodes (Builded in 1400 ms, counted in 60 ms).
#Fib. no. 22 has 17710 internal nodes (Builded in 810 ms, counted in 40 ms).
#Fib. no. 23 has 75024 internal nodes (Builded in 3619 ms, counted in 150 ms).
#Fib. no. 24 has 46367 internal nodes (Builded in 2430 ms, counted in 89 ms).
#Fib. no. 25 has 196417 internal nodes (Builded in 10339 ms, counted in 390 ms).
#Fib. no. 26 has 121392 internal nodes (Builded in 6850 ms, counted in 239 ms).
#Fib. no. 27 has 514228 internal nodes (Builded in 31740 ms, counted in 1039 ms).
